{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #K-diff Pairs in an Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #two-pointers #binary-search #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #双指针 #二分查找 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findPairs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #数组中的 k-diff 数对"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组&nbsp;<code>nums</code> 和一个整数&nbsp;<code>k</code>，请你在数组中找出<strong> 不同的&nbsp;</strong>k-diff 数对，并返回不同的 <strong>k-diff 数对</strong> 的数目。</p>\n",
    "\n",
    "<p><strong>k-diff</strong>&nbsp;数对定义为一个整数对 <code>(nums[i], nums[j])</code><strong> </strong>，并满足下述全部条件：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= i, j &lt; nums.length</code></li>\n",
    "\t<li><code>i != j</code></li>\n",
    "\t<li><code>|nums[i] - nums[j]| == k</code></li>\n",
    "</ul>\n",
    "\n",
    "<p><strong>注意</strong>，<code>|val|</code> 表示 <code>val</code> 的绝对值。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [3, 1, 4, 1, 5], k = 2\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>数组中有两个 2-diff 数对, (1, 3) 和 (3, 5)。\n",
    "尽管数组中有两个 1 ，但我们只应返回不同的数对的数量。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1, 2, 3, 4, 5], k = 1\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>数组中有四个 1-diff 数对, (1, 2), (2, 3), (3, 4) 和 (4, 5) 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1, 3, 1, 5, 4], k = 0\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>数组中只有一个 0-diff 数对，(1, 1) 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>-10<sup>7</sup> &lt;= nums[i] &lt;= 10<sup>7</sup></code></li>\n",
    "\t<li><code>0 &lt;= k &lt;= 10<sup>7</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [k-diff-pairs-in-an-array](https://leetcode.cn/problems/k-diff-pairs-in-an-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [k-diff-pairs-in-an-array](https://leetcode.cn/problems/k-diff-pairs-in-an-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,1,4,1,5]\\n2', '[1,2,3,4,5]\\n1', '[1,3,1,5,4]\\n0']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        #print(nums)\n",
    "        size=len(nums)\n",
    "        if size<2:\n",
    "            return 0\n",
    "        left, right=0,1\n",
    "        count=0\n",
    "        while (left<size) :\n",
    "            while (right<size and nums[right]-nums[left]<k) :\n",
    "                right+=1\n",
    "        \n",
    "            if right<size and nums[right]-nums[left]==k:\n",
    "                count+=1\n",
    "            while (left+1<size and nums[left+1]==nums[left]) :\n",
    "                left+=1\n",
    "            left+=1\n",
    "            right=left+1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        n, y, res = len(nums), 0, 0\n",
    "        for x in range(n):\n",
    "            if x == 0 or nums[x] != nums[x - 1]:\n",
    "                while y < n and (nums[y] < nums[x] + k or y <= x):\n",
    "                    y += 1\n",
    "                if y < n and nums[y] == nums[x] + k:\n",
    "                    res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        n, y, res = len(nums), 0, 0\n",
    "        for x in range(n):\n",
    "            if x == 0 or nums[x] != nums[x - 1]:\n",
    "                while y < n and (nums[y] < nums[x] + k or y <= x):\n",
    "                    y += 1\n",
    "                if y < n and nums[y] == nums[x] + k:\n",
    "                    res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        i=0\n",
    "        ans=0\n",
    "        j=1\n",
    "        while i<len(nums):\n",
    "            if i>0 and nums[i]==nums[i-1]:\n",
    "                i+=1\n",
    "                continue\n",
    "            j=i+1\n",
    "            while j<len(nums):\n",
    "                if nums[j]-nums[i]==k:\n",
    "                    ans+=1\n",
    "                    break\n",
    "                j+=1\n",
    "            i+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        if k < 0:\n",
    "            return 0\n",
    "        \n",
    "        nums.sort()\n",
    "        count = left = 0\n",
    "        right = 1\n",
    "        \n",
    "        while right < len(nums):\n",
    "            diff = abs(nums[right] - nums[left])\n",
    "            \n",
    "            if diff < k:\n",
    "                right += 1\n",
    "            elif diff > k:\n",
    "                left += 1\n",
    "            else:\n",
    "                count += 1\n",
    "                left += 1\n",
    "                right += 1\n",
    "                while left < len(nums) and nums[left] == nums[left-1]:\n",
    "                    left += 1\n",
    "                while right < len(nums) and nums[right] == nums[right-1]:\n",
    "                    right += 1\n",
    "            if left >= right:\n",
    "                right = left + 1\n",
    "                \n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def findPairs(self, nums: List[int], k: int) -> int:\n",
    "#         nums.sort(reverse = True)\n",
    "#         left = 0\n",
    "#         right = len(nums) - 1\n",
    "#         ant = 0\n",
    "#         for i in range(len(nums)-1):\n",
    "#             while left <= right:\n",
    "#                 mid = (left + right) // 2\n",
    "#                 if nums[right] - nums[left] > k:\n",
    "#                     left = mid + 1\n",
    "#                 elif nums[right] - nums[left] < k:\n",
    "#                     right = mid - 1\n",
    "#                 else:\n",
    "#                     ant += 1\n",
    "#\n",
    "#             left = i+1\n",
    "#         return ant\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        ant = 0\n",
    "        left = 0\n",
    "        right = 1\n",
    "        while left < len(nums) and right < len(nums):\n",
    "            if left == right or nums[right] - nums[left] < k:\n",
    "                right += 1\n",
    "            elif nums[right] - nums[left] > k:\n",
    "                left += 1\n",
    "            else:\n",
    "                ant += 1\n",
    "                left += 1\n",
    "                right += 1\n",
    "                while right < len(nums) and nums[right] == nums[right-1]:\n",
    "                    right += 1\n",
    "                while left < len(nums) and nums[left] == nums[left-1]:\n",
    "                    left += 1\n",
    "        return ant\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        result = 0\n",
    "        visited = []\n",
    "        if k == 0:\n",
    "            for i in nums:\n",
    "                if nums.count(i) > 1 and i not in visited:\n",
    "                    result += 1\n",
    "                    visited.append(i)\n",
    "        else:\n",
    "            for i in nums:\n",
    "                if i in visited:\n",
    "                    continue\n",
    "                if i + k in nums and i + k not in visited:\n",
    "                    result += 1\n",
    "                if i - k in nums and i - k not in visited:\n",
    "                    result += 1\n",
    "                visited.append(i)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        #def findsums(nums, target):\n",
    "        #    left = 0\n",
    "        #    right = len(nums) - 1\n",
    "        #   while left < right:\n",
    "\n",
    "        nums.sort()\n",
    "        last = float(\"inf\")\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if nums[i] == last:\n",
    "                continue\n",
    "            left = i + 1\n",
    "            right = n - 1\n",
    "            while left <= right:\n",
    "                mid = (left + right) // 2\n",
    "                if nums[mid] > nums[i] + k:\n",
    "                    right = mid - 1\n",
    "                elif nums[mid] < nums[i] + k:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    ans = ans + 1\n",
    "                    break\n",
    "            last = nums[i]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "                hash_map =  {}\n",
    "\n",
    "                for num in nums:\n",
    "                    if num in hash_map.keys():\n",
    "                        hash_map[num] += 1\n",
    "                    else:\n",
    "                        hash_map[num] = 1\n",
    "\n",
    "                count = 0\n",
    "                for num, times in hash_map.items():\n",
    "                    if k == 0:\n",
    "                        if times >= 2:\n",
    "                            count += 1\n",
    "                    else:\n",
    "                        if num + k in hash_map.keys():\n",
    "                            count += 1\n",
    "\n",
    "                return count  \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        if k < 0:\n",
    "            return 0\n",
    "        \n",
    "        nums.sort()\n",
    "        count = left = 0\n",
    "        right = 1\n",
    "        \n",
    "        while right < len(nums):\n",
    "            diff = abs(nums[right] - nums[left])\n",
    "            \n",
    "            if diff < k:\n",
    "                right += 1\n",
    "            elif diff > k:\n",
    "                left += 1\n",
    "            else:\n",
    "                count += 1\n",
    "                left += 1\n",
    "                right += 1\n",
    "                while left < len(nums) and nums[left] == nums[left-1]:\n",
    "                    left += 1\n",
    "                while right < len(nums) and nums[right] == nums[right-1]:\n",
    "                    right += 1\n",
    "            if left >= right:\n",
    "                right = left + 1\n",
    "                \n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        count = 0\n",
    "        for i in range(len(nums)):\n",
    "            if i != 0 and nums[i] == nums[i - 1]:\n",
    "                continue\n",
    "            j = i + 1\n",
    "            while j < len(nums):\n",
    "                if nums[j] - nums[i] == k:\n",
    "                    count += 1\n",
    "                    break\n",
    "                j += 1\n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        print(nums)\n",
    "        \n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n-1):\n",
    "            if i > 0 and nums[i] == nums[i-1]:\n",
    "                continue\n",
    "                \n",
    "\n",
    "            L,R = i+1,n-1\n",
    "#             print(i,L,R)\n",
    "            while L<=R:\n",
    "                M = (L+R)//2\n",
    "                if nums[M] - nums[i] < k:\n",
    "                    L = M+1\n",
    "                else:\n",
    "                    R = M-1\n",
    "                    \n",
    "            if (i+1)<=L<=(n-1) and (nums[L]-nums[i]==k):\n",
    "                res += 1\n",
    "\n",
    "        return(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        def binarySearch(i, j, target, nums):\n",
    "            while i <= j:\n",
    "                mid = (i+j) >> 1\n",
    "                if nums[mid] == target: return True\n",
    "                elif nums[mid] > target: j = mid-1\n",
    "                else: i = mid + 1\n",
    "            return False\n",
    "            \n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if i and nums[i] == nums[i-1]: continue\n",
    "            if binarySearch(i+1, n-1, k+nums[i], nums):\n",
    "                res +=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        new = []\n",
    "        tag = {}\n",
    "        ans = 0\n",
    "        for i in nums:\n",
    "            if i not in tag:\n",
    "                tag[i] = 0\n",
    "                new.append(i)\n",
    "            tag[i] += 1\n",
    "        if k == 0:\n",
    "            for i in tag:\n",
    "                if tag[i] > 1:\n",
    "                    ans += 1\n",
    "            return ans\n",
    "        new.sort()\n",
    "        left = 0\n",
    "        end = len(new)\n",
    "        for right in range(end):\n",
    "            while left < right and new[right] > new[left] + k:\n",
    "                left += 1\n",
    "            if new[right] == new[left] + k:\n",
    "                left += 1\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        s=set()\n",
    "        a={}\n",
    "        num=0\n",
    "        for i in nums:\n",
    "            if i in a.keys():\n",
    "                a[i]+=1\n",
    "            else:\n",
    "                a[i]=1\n",
    "        if k==0:\n",
    "            for i in a.keys():\n",
    "                if a[i]>=2:\n",
    "                    num+=1\n",
    "        else:\n",
    "            for i in a.keys():\n",
    "                if k+i in a.keys():\n",
    "                    num+=1\n",
    "        return num\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        mp = {}\n",
    "        for x in nums:\n",
    "            if x in mp:\n",
    "                mp[x] += 1\n",
    "            else:\n",
    "                mp[x] = 1\n",
    "        ans = 0\n",
    "        for x, cnt in mp.items():\n",
    "            if k == 0: # 特判k=0时的情况，需要看一个数是否出现至少两次\n",
    "                ans += (cnt >= 2)\n",
    "            else:\n",
    "                ans += (x+k in mp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        res=0\n",
    "        num_counter=collections.Counter(nums)\n",
    "\n",
    "        for val in num_counter:\n",
    "            if k!=0 and val+k in num_counter:\n",
    "                res+=1\n",
    "            if k==0 and num_counter[val]>1:\n",
    "                res+=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        myhash = {}\n",
    "        res = 0\n",
    "        nums.sort()\n",
    "        for num in nums:\n",
    "            myhash[num] = myhash.get(num,0)+1\n",
    "        for k1,v1 in myhash.items():\n",
    "            if k == 0:\n",
    "                if v1>1:\n",
    "                    res+=1\n",
    "            else:\n",
    "                if k1+k in myhash:\n",
    "                    res+=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        dic={}\n",
    "        res=0#计数\n",
    "        for n in nums:\n",
    "            if n in dic:\n",
    "                dic[n]+=1\n",
    "            else:\n",
    "                dic[n]=1\n",
    "        for n,count in dic.items():\n",
    "            if k==0:\n",
    "            #当差值为0，只要一个出现两次及以上就可以满足\n",
    "                if count>=2:\n",
    "                   res+=1\n",
    "            elif k!=0:\n",
    "                if n+k in dic:\n",
    "                   res+=1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        m = defaultdict(int)\n",
    "        for num in nums:\n",
    "            m[num] += 1\n",
    "        \n",
    "        cnt = 0\n",
    "        for num in m:\n",
    "            if k == 0:\n",
    "                if m[num] >= 2:\n",
    "                    cnt += 1\n",
    "            else:\n",
    "                if num - k in m:\n",
    "                    cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        from collections import Counter\n",
    "        dic = Counter(nums)\n",
    "        res = 0\n",
    "        used = []\n",
    "        \n",
    "        if k==0:\n",
    "            for value in dic.values():\n",
    "                if value>=2:\n",
    "                    res+=1\n",
    "        else :\n",
    "            all_keys = dic.keys()\n",
    "            # print(all_keys)\n",
    "            for key in all_keys:\n",
    "                # 小前大后\n",
    "                if key-k in all_keys and key-k not in used:\n",
    "                    res+=1\n",
    "                if key+k in all_keys and key+k not in used:\n",
    "                    res+=1\n",
    "                used.append(key)\n",
    "        return res\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        # 如果数组长度小于等于1，则没有数组对返回0\n",
    "        if n <= 1:\n",
    "            return 0\n",
    "        # 定义两个指针，left表示较小的数，right表示较大的数\n",
    "        left, right = 0, 1\n",
    "        res = []\n",
    "        while True:\n",
    "            cur_diff = nums[right] - nums[left]\n",
    "            # 当cur_diff>diff的时候，两个指针都往右移动\n",
    "            while right < n and cur_diff > k:\n",
    "                left += 1\n",
    "                if left >= right:\n",
    "                    right += 1\n",
    "                if right < n:\n",
    "                    cur_diff = nums[right] - nums[left]\n",
    "            # 如果移动到最右边，差值仍然大于k，说明没有找到\n",
    "            if right == n:\n",
    "                return len(res)\n",
    "            # 如果找到cur_diff<=k\n",
    "            while cur_diff <= k:\n",
    "                # 如果cur_diff==k,记录,并将左指针右移\n",
    "                if nums[right] - nums[left] == k:\n",
    "                    if (nums[left], nums[right]) not in res:\n",
    "                        res.append((nums[left], nums[right]))\n",
    "                    left += 1\n",
    "                    # 如果左指针和右指针重合了，则将右指针也移动一位\n",
    "                    if left >= right:\n",
    "                        right += 1\n",
    "                    if right < n:\n",
    "                        cur_diff = nums[right] - nums[left]\n",
    "                # 如果cur_diff<k，右指针右移\n",
    "                while right < n and cur_diff < k:\n",
    "                    right += 1\n",
    "                    if right < n:\n",
    "                        cur_diff = nums[right] - nums[left]\n",
    "                if right >= n:\n",
    "                    return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        numset = set(nums)\n",
    "        if k == 0:\n",
    "            shudui = 0\n",
    "            for _ in numset:\n",
    "                if nums.count(_) > 1:\n",
    "                    shudui += 1\n",
    "            return shudui\n",
    "        shudui = 0\n",
    "        for each in numset:\n",
    "            if each + k in numset:\n",
    "                shudui += 1\n",
    "        return shudui\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        i = 0\n",
    "        j = 1\n",
    "        ans = 0\n",
    "        kdiff = []\n",
    "        while j < len(nums):\n",
    "            if nums[j] - nums[i] == k: \n",
    "                if [nums[i], nums[j]] not in kdiff:\n",
    "                    ans += 1\n",
    "                    kdiff.append([nums[i], nums[j]])\n",
    "                j += 1\n",
    "                i += 1\n",
    "            elif nums[j] - nums[i] > k: \n",
    "                i += 1\n",
    "                if i == j: j += 1\n",
    "            else: j += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        numset = set(nums)\n",
    "        if k == 0:\n",
    "            shudui = 0\n",
    "            for _ in numset:\n",
    "                if nums.count(_) > 1:\n",
    "                    shudui += 1\n",
    "            return shudui\n",
    "        shudui = 0\n",
    "        for each in numset:\n",
    "            if each + k in numset:\n",
    "                shudui += 1\n",
    "        return shudui\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        nums.sort()\n",
    "        cache = {}\n",
    "        for i in nums:\n",
    "            if i-k in cache and cache[i-k] != -1:\n",
    "                res += 1\n",
    "                cache[i-k] = -1\n",
    "            if i not in cache:\n",
    "                cache[i] = 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        cnt = Counter(nums)\n",
    "        for num in cnt:\n",
    "            if k == 0:\n",
    "                if cnt[num] > 1:\n",
    "                    ans += 1\n",
    "            else:\n",
    "                if num + k in cnt:\n",
    "                    ans += 1\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        from collections import Counter\n",
    "        dic = Counter(nums)\n",
    "        res = 0\n",
    "        used = []\n",
    "        \n",
    "        if k==0:\n",
    "            for value in dic.values():\n",
    "                if value>=2:\n",
    "                    res+=1\n",
    "        else :\n",
    "            all_keys = dic.keys()\n",
    "            # print(all_keys)\n",
    "            for key in all_keys:\n",
    "                # 小前大后\n",
    "                if key-k in all_keys and key-k not in used:\n",
    "                    res+=1\n",
    "                if key+k in all_keys and key+k not in used:\n",
    "                    res+=1\n",
    "                used.append(key)\n",
    "        return res\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        hash_table = {}\n",
    "        result = 0\n",
    "        for num in nums:\n",
    "            if num in hash_table:\n",
    "                hash_table[num] += 1\n",
    "            else:\n",
    "                hash_table[num] = 1\n",
    "        print(hash_table)\n",
    "        for num in hash_table:\n",
    "            if k == 0 and hash_table[num] > 1:\n",
    "                result += 1\n",
    "            elif k != 0 and num + k in hash_table:\n",
    "                result += 1\n",
    "        \n",
    "        return result \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        hashmap = set(); used = set(); ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] in hashmap and k==0:\n",
    "                ans += 1\n",
    "                hashmap.remove(nums[i])\n",
    "                used.add(nums[i])\n",
    "                \n",
    "            elif nums[i] not in hashmap and nums[i] not in used:\n",
    "                if nums[i]-k in hashmap:\n",
    "                    ans += 1\n",
    "                if nums[i]+k in hashmap:\n",
    "                    ans += 1\n",
    "                hashmap.add(nums[i])\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        i = 0\n",
    "        j = 1\n",
    "        ans = 0\n",
    "        kdiff = set()\n",
    "        while j < len(nums):\n",
    "            if nums[j] - nums[i] == k: \n",
    "                if nums[i] not in kdiff:\n",
    "                    ans += 1\n",
    "                    kdiff.add(nums[i])\n",
    "                j += 1\n",
    "                i += 1\n",
    "            elif nums[j] - nums[i] > k: \n",
    "                i += 1\n",
    "                if i == j: j += 1\n",
    "            else: j += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        if k < 0:\n",
    "            return 0\n",
    "    \n",
    "        unique_nums = set(nums)\n",
    "        \n",
    "        if k == 0:\n",
    "            # 对于 k = 0 的情况，需要找出数组中出现次数大于 1 的元素\n",
    "            return len([num for num in unique_nums if nums.count(num) > 1])\n",
    "        else:\n",
    "            # 对于 k != 0 的情况，需要找出数组中所有满足 nums[i] + k = nums[j] 的数对\n",
    "            return len([num for num in unique_nums if num + k in unique_nums])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        res=0\n",
    "        if k==0:\n",
    "            counter=dict()\n",
    "            for i in range(len(nums)):\n",
    "                counter[nums[i]]=counter.get(nums[i],0)+1\n",
    "            for key in counter:\n",
    "                if counter[key]>=2:\n",
    "                    res+=1\n",
    "        if k>=1:\n",
    "            _nums=list(set(nums))\n",
    "            _nums.sort()\n",
    "            label=[0]*len(_nums)\n",
    "            for i in range(len(_nums)):\n",
    "                if _nums[i]+k in _nums:\n",
    "                    res+=1\n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        if k == 0:\n",
    "            hash = Counter(nums)\n",
    "            for k,v in hash.items():\n",
    "                if v >= 2:\n",
    "                    ans += 1\n",
    "            return ans\n",
    "        i = 0\n",
    "        j = 1\n",
    "        nums = list(set(nums))\n",
    "        nums.sort()\n",
    "        while i < j < len(nums):\n",
    "            while j < len(nums) and nums[j] - nums[i] == k:\n",
    "                i += 1\n",
    "                j += 1\n",
    "                ans += 1\n",
    "            if j < len(nums) and nums[j] - nums[i] >= k:\n",
    "                i += 1\n",
    "            elif j < len(nums):\n",
    "                j += 1\n",
    "            if i == j:\n",
    "                j += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        if k == 0:\n",
    "            newlist = []\n",
    "            same = []\n",
    "            for x in nums:\n",
    "                if x not in newlist:\n",
    "                    newlist.append(x)\n",
    "                else:\n",
    "                    same.append(x)\n",
    "            return len(set(same))\n",
    "        nums = sorted(list(set(nums)))\n",
    "        count = 0\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i+1, len(nums)):\n",
    "                if abs(nums[j] - nums[i]) == k:\n",
    "                    count += 1\n",
    "                elif abs(nums[j] - nums[i]) > k:\n",
    "                    break\n",
    "                \n",
    "        return count \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "    \n",
    "        if not nums:\n",
    "            return 0\n",
    "            \n",
    "        if k< 0:\n",
    "            return 0\n",
    "            \n",
    "        if k == 0:\n",
    "            nums_dict = collections.Counter()\n",
    "            for num in nums:\n",
    "                nums_dict[num] += 1\n",
    "            return sum(1 for val in nums_dict.values() if val > 1)\n",
    "            \n",
    "        nums_ = set(nums)\n",
    "        return sum(1 for num in nums_ if num+k in nums_)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        if k==0:\n",
    "            dic = dict()\n",
    "            for i in nums:\n",
    "                if i not in dic:\n",
    "                    dic[i]=1\n",
    "                else: dic[i]+=1\n",
    "            for m,n in dic.items():\n",
    "                if n>1: res+=1\n",
    "        else:\n",
    "            nums = set(nums)\n",
    "            for i in nums:\n",
    "                if i-k in nums:\n",
    "                    res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        \n",
    "        if k == 0:  # k=0意味着需要找到数组重复数字的个数\n",
    "            s = collections.Counter(nums)\n",
    "            res = 0\n",
    "            for n, c in s.items():\n",
    "                if c > 1:\n",
    "                    res += 1\n",
    "            return res\n",
    "        else:\n",
    "            nums_set = sorted(set(nums))  # 消去重复的数字并排序\n",
    "            may = set()\n",
    "            res = 0\n",
    "            for n in nums_set: \n",
    "                # 对于数字n，可能的数对为n+k，将他添加到may中\n",
    "                #{1, 3, 4, 5}\n",
    "                if n in may:\n",
    "                    res += 1\n",
    "                may.add(n+k)\n",
    "               \n",
    "            return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        if len(nums) == 1: return 0\n",
    "        nums.sort()\n",
    "        s = set()\n",
    "        i, j = 0, 1\n",
    "        while j <= len(nums) - 1:\n",
    "            if nums[j] - nums[i] == k:\n",
    "                s.add((nums[i], nums[j]))\n",
    "                i += 1\n",
    "                j += 1\n",
    "            elif nums[j] - nums[i] > k and i < j - 1:\n",
    "                i += 1\n",
    "            elif nums[j] - nums[i] < k:\n",
    "                j += 1\n",
    "            elif nums[j] - nums[i] > k and i == j - 1:\n",
    "                i += 1\n",
    "                j += 1\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        nums.sort()\n",
    "        s = set()\n",
    "        length = len(nums)\n",
    "\n",
    "        left = 0\n",
    "        right = 1\n",
    "\n",
    "        while right < length:\n",
    "            if nums[right] - nums[left] < k:\n",
    "                right += 1\n",
    "            elif nums[right] - nums[left] > k:\n",
    "                if right - left > 1:\n",
    "                    left += 1\n",
    "                elif right - left == 1:\n",
    "                    left += 1\n",
    "                    right += 1\n",
    "            else:\n",
    "                tmp = (nums[left], nums[right])\n",
    "                if tmp not in s:\n",
    "                    s.add(tmp)\n",
    "                    res += 1\n",
    "                left += 1\n",
    "                right += 1\n",
    "\n",
    "        return res                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        res = set()\n",
    "        nums.sort(reverse=False)\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i+1, len(nums)):\n",
    "                if nums[j] - nums[i] == k:\n",
    "                    res.add((nums[i], nums[j]))\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        n=len(nums)\n",
    "        nums=sorted(nums)\n",
    "        dic={}\n",
    "        for i in range(len(nums)):\n",
    "            dic[nums[i]]=i\n",
    "        st=0\n",
    "        fs=set()\n",
    "        res=0\n",
    "        while st<n:\n",
    "            ed=dic[nums[st]]\n",
    "            if nums[st] not in fs and (nums[st]+k) in dic.keys():\n",
    "                fs.add(nums[st])\n",
    "                if dic[nums[st]+k]!=st:\n",
    "                    res+=1\n",
    "            while st+1<n and nums[st]==nums[st+1]:\n",
    "                st+=1\n",
    "            st+=1\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        if len(nums) == 1:\n",
    "            return 0\n",
    "        if k==0:\n",
    "            times = {}\n",
    "            for i in nums:\n",
    "                if i in times:\n",
    "                    times[i]+=1\n",
    "                else:\n",
    "                    times[i] = 1\n",
    "            result = 0\n",
    "            for i in times:\n",
    "                if times[i]>1:\n",
    "                    result+=1\n",
    "            return result\n",
    "        else:\n",
    "            elem = set()\n",
    "            for i in nums:\n",
    "                elem.add(i)\n",
    "            result = 0\n",
    "            elem1 = elem.copy()\n",
    "            for i in elem1:\n",
    "                flg = False\n",
    "                if i+k in elem:\n",
    "                    result+=1\n",
    "                    flg = True\n",
    "                if i-k in elem:\n",
    "                    result+=1\n",
    "                    flg = True\n",
    "                if flg:\n",
    "                    # print(elem)\n",
    "                    # print(i)\n",
    "                    elem.remove(i)\n",
    "            return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        # 定义一个集合，记录已经选择过的元素\n",
    "        selected = set()\n",
    "        n = len(nums)\n",
    "        if n <= 1:\n",
    "            return 0\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                if nums[j] - nums[i] == k:\n",
    "                    if (nums[i], nums[j]) not in selected:\n",
    "                        selected.add((nums[i], nums[j]))\n",
    "                elif nums[j] - nums[i] > k:\n",
    "                    break\n",
    "        return len(selected)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        freq=Counter(nums)\n",
    "        ans=0\n",
    "        if k==0:\n",
    "            for key,v in freq.items():\n",
    "                if v>=2:\n",
    "                    ans+=1\n",
    "            return ans\n",
    "        lst=set(freq.keys())\n",
    "        # lst.sort()\n",
    "        # print(lst)\n",
    "        n=len(lst)\n",
    "        for v in lst:\n",
    "            if v-k in lst:\n",
    "                ans+=1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        if k== 0:\n",
    "            count = Counter(nums)\n",
    "            ans = 0\n",
    "            for n in count:\n",
    "                if count[n] > 1: ans +=1\n",
    "            return ans\n",
    "        nums = set(nums)\n",
    "        pairs = {n:n + k for n in nums}\n",
    "        ans = 0\n",
    "        for n in pairs:\n",
    "            if pairs[n] in nums:\n",
    "                ans +=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        \n",
    "        coop = set()\n",
    "        nums.sort()\n",
    "        out = 0\n",
    "        for left, x in enumerate(nums):\n",
    "            right = left+1\n",
    "            if right ==len(nums):\n",
    "                break\n",
    "            while abs(nums[right]-x)<=abs(k):\n",
    "                if k == 0 and abs(nums[right]-x)==0:\n",
    "                    coop.add((x,nums[right]))\n",
    "                elif abs(nums[right]-x) == abs(k):\n",
    "                    coop.add((x,nums[right]))\n",
    "\n",
    "                right += 1\n",
    "                if right == len(nums):\n",
    "                    break\n",
    "        \n",
    "        return len(coop)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort(reverse = True)\n",
    "\n",
    "        if nums[0]-nums[-1]<k:\n",
    "            return 0\n",
    "        \n",
    "        l = set()\n",
    "\n",
    "        for i in range(len(nums)-1):\n",
    "            for j in range(i+1,len(nums)):\n",
    "                if nums[i]-nums[j] == k:\n",
    "                    l.add((nums[i],nums[j]))\n",
    "                elif nums[i]-nums[j]<k:\n",
    "                    continue\n",
    "                else:\n",
    "                    break\n",
    "        \n",
    "\n",
    "\n",
    "        return len(l)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        used = set()\n",
    "        seen = set()\n",
    "        for i in nums:\n",
    "            target1 = i + k\n",
    "            target2 = i - k \n",
    "            if target1 in seen:\n",
    "                used.add(i)\n",
    "            if target2 in seen:\n",
    "                used.add(target2)\n",
    "            seen.add(i)\n",
    "        return len(used)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        result = []\n",
    "        p0, p1 = 0, 1\n",
    "        while p1 < n:\n",
    "            if abs(nums[p0] - nums[p1]) == k:\n",
    "                result.append((nums[p0], nums[p1]))\n",
    "                p0 += 1\n",
    "                p1 += 1\n",
    "            else:\n",
    "                if abs(nums[p0] - nums[p1]) > k:\n",
    "                    p0 += 1\n",
    "                    if p0 == p1:\n",
    "                        p1 += 1\n",
    "                else:\n",
    "                    p1 += 1\n",
    "        return len(set(result))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        visited, res = set(), set()\n",
    "        for num in nums:\n",
    "            if num - k in visited:\n",
    "                res.add(num - k)\n",
    "            if num + k in visited:\n",
    "                res.add(num)\n",
    "            visited.add(num)\n",
    "        return len(res) \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        visited, res = set(), set()\n",
    "        for num in nums:\n",
    "            if num - k in visited:\n",
    "                res.add(num-k)\n",
    "            if num + k in visited:\n",
    "                res.add(num)\n",
    "            visited.add(num)\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        dic,ans = set(),set()\n",
    "        for num in nums:\n",
    "            if num - k in ans:\n",
    "                dic.add(num - k)\n",
    "            if num + k in ans:\n",
    "                dic.add(num)\n",
    "            ans.add(num)\n",
    "        return len(dic)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        visited = set()\n",
    "        res = set()\n",
    "\n",
    "        for num in nums:\n",
    "            if num + k in visited:\n",
    "                res.add(num)\n",
    "            if num - k in visited:\n",
    "                res.add(num-k)\n",
    "            visited.add(num)\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        hash_set = set()\n",
    "        num_set = set()\n",
    "        for n in nums:\n",
    "            if n + k in num_set:\n",
    "                hash_set.add(n)\n",
    "            if n - k in num_set:\n",
    "                hash_set.add(n-k)\n",
    "            num_set.add(n)\n",
    "        return len(hash_set)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "[3,1,4,1,5]\n",
    "2\n",
    "[1,2,3,4,5]\n",
    "1\n",
    "[1,3,1,5,4]\n",
    "0\n",
    "[-1,-2,-3]\n",
    "1\n",
    "\n",
    "1 <= nums.length <= 1e4\n",
    "-1e7 <= nums[i] <= 1e7\n",
    "0 <= k <= 1e7\n",
    "\n",
    "Array, Hash Table, Two Pointers, Binary Search, Sorting\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        cache = set()\n",
    "        used = set() # record the smaller one\n",
    "        for x in nums:\n",
    "            if x-k in cache:\n",
    "                used.add(x-k)\n",
    "            if x+k in cache:\n",
    "                used.add(x)\n",
    "            cache.add(x)\n",
    "        return len(used)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # cnt =  collections.Counter(nums)\n",
    "\n",
    "        # n = len(nums)\n",
    "        # res = 0\n",
    "\n",
    "        # if k == 0:\n",
    "        #     for k in cnt:\n",
    "        #         if cnt[k] >= 2:\n",
    "        #             res += 1\n",
    "        #     return res\n",
    "        # for i in range(n):\n",
    "\n",
    "        #     if nums[i] not in cnt:\n",
    "        #         continue\n",
    "            \n",
    "        #     if nums[i] + k in cnt:\n",
    "        #         res += 1\n",
    "        #     if nums[i] - k in cnt:\n",
    "        #         res += 1\n",
    "        #     del cnt[nums[i]]\n",
    "        \n",
    "        # return res\n",
    "\n",
    "\n",
    "\n",
    "        visited, res = set(), set()\n",
    "\n",
    "        for num in nums:\n",
    "\n",
    "            if num - k in visited:\n",
    "                res.add(num - k)\n",
    "\n",
    "            if num + k in visited:\n",
    "                res.add(num)\n",
    "            \n",
    "            visited.add(num)\n",
    "        return len(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        visited, res = set(), set()#哈希表不能存两个及以上相同的值\n",
    "        for num in nums:\n",
    "            if num - k in visited:\n",
    "                res.add(num)\n",
    "            if num + k in visited:\n",
    "                res.add(num+k)\n",
    "            visited.add(num)\n",
    "        return len(res) \n",
    "        # n = set()\n",
    "        # i = 0\n",
    "        # if k == 0:\n",
    "        #     for i in range(len(nums)):\n",
    "        #         for j in range(i+1,len(nums)):\n",
    "        #             if nums[i] == nums[j]:\n",
    "        #                 n.add(nums[i])\n",
    "            \n",
    "        # else:\n",
    "        #     num = []\n",
    "        #     for i in range(len(nums)):\n",
    "        #         if nums[i] not in num:\n",
    "        #             num.append(nums[i])\n",
    "\n",
    "        #     for i in range(len(num)):\n",
    "        #         for j in range(i+1,len(num)):\n",
    "        #             if num[i] - num[j] == k:\n",
    "        #                 n.add(num[j])\n",
    "        #             elif num[j] - num[i] == k:\n",
    "        #                 n.add(num[i]) \n",
    "        # return len(n)  超时 \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "       #因为要求不同的diff-k,运用set\n",
    "       numset=set()#原列表的相同数值去重\n",
    "       resset=set()#满足的结果去重\n",
    "       for num in nums:\n",
    "           if num-k in numset:\n",
    "              #resset.add((num-k,num))\n",
    "              resset.add(num-k)\n",
    "              #两个数值中较小值加入,两个括号\n",
    "           if num+k in numset:\n",
    "              #resset.add((num,num+k))\n",
    "              resset.add(num)\n",
    "           numset.add(num)\n",
    "           #只将数对的较小值放入resset,不影响结果正确性，判断完以后在将当前元素放入numset,作为后续判断的num\n",
    "       return len(resset)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        res=set()\n",
    "        visited=set()\n",
    "        for i in nums:\n",
    "            if i-k in visited:\n",
    "                res.add(i)\n",
    "            if i+k in visited:\n",
    "                res.add(i+k)\n",
    "            visited.add(i)\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        visited, res = set(), set()\n",
    "        for num in nums:\n",
    "            if num - k in visited:\n",
    "                res.add(num - k)\n",
    "            if num + k in visited:\n",
    "                res.add(num)\n",
    "            visited.add(num)\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    利用集合性质处理的解法\n",
    "    \"\"\"\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        set_nums = set(nums)\n",
    "        if k == 0:\n",
    "            return len({i for i in nums if nums.count(i) >= 2})\n",
    "\n",
    "        nums_add_k = {i + k for i in set_nums}\n",
    "        res = len(set_nums & nums_add_k)\n",
    "        return res\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     \"\"\"\n",
    "#     哈希表\n",
    "#     \"\"\"\n",
    "#     def findPairs(self, nums: List[int], k: int) -> int:\n",
    "#         dict_nums = defaultdict(int)\n",
    "#         for num in nums:\n",
    "#             dict_nums[num] += 1\n",
    "\n",
    "#         res = 0\n",
    "#         for item, value in dict_nums.items():\n",
    "#             if k == 0 and value >= 2:\n",
    "#                 res += 1\n",
    "#             elif k > 0 and (item + k) in dict_nums:\n",
    "#                 res += 1\n",
    "#         return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        res = set()\n",
    "        visited = set()\n",
    "        for num in nums:\n",
    "            if num - k in visited:\n",
    "                res.add(num - k)\n",
    "            if num + k in visited:\n",
    "                res.add(num)\n",
    "            visited.add(num)\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        result = set()\n",
    "        visited = set()\n",
    "        for num in nums:\n",
    "            if num+k in visited:\n",
    "                result.add(num)\n",
    "            if num-k in visited:\n",
    "                result.add(num-k)\n",
    "            visited.add(num)\n",
    "        return len(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        if k == 0:\n",
    "            a = dict()\n",
    "            b = set()\n",
    "            for num in nums:\n",
    "                if num in a:\n",
    "                    b.add(num)\n",
    "                else:\n",
    "                    a[num] = 1\n",
    "            return len(b)\n",
    "        a = set(nums)\n",
    "        b = set()\n",
    "        for num in nums:\n",
    "            if num+k in a:\n",
    "                b.add((num, num+k))\n",
    "        return len(b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        count = defaultdict(int)\n",
    "        for num in nums:\n",
    "            count[num] += 1\n",
    "        \n",
    "        if k == 0:\n",
    "            return sum(count[k]>=2 for k in count)\n",
    "\n",
    "        nums = list(set(nums))\n",
    "\n",
    "        dct = defaultdict(int)\n",
    "        ans = 0\n",
    "        for num in count:\n",
    "            ans += dct[num-k]\n",
    "            ans += dct[num+k]\n",
    "            dct[num] += 1\n",
    "            dct[num] = min(1, dct[num])\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        lst=list(set(sorted(nums)))\n",
    "        n=len(lst)\n",
    "        if k==0:\n",
    "            c=0\n",
    "            for num in lst:\n",
    "                if nums.count(num)>1:\n",
    "                    c+=1 \n",
    "            return c\n",
    "        if k>0:\n",
    "            li=[]\n",
    "            for i in range(n):\n",
    "                li.append(int(lst[i])+k)\n",
    "            ll=set(li)&set(lst)\n",
    "            return len(ll)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        s=set()\n",
    "        h=dict()\n",
    "\n",
    "        for num in nums:\n",
    "            if num not in h:\n",
    "                h[num]=1\n",
    "            else:\n",
    "                h[num]+=1\n",
    "\n",
    "        for num in nums:\n",
    "            if num-k not in h:\n",
    "                continue\n",
    "            if k==0:\n",
    "                if h[num]>=2:\n",
    "                    s.add((num,num-k))\n",
    "            else:\n",
    "                s.add((num,num-k))\n",
    "        return len(s)\n",
    "      \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        resList=[]\n",
    "        if k == 0:\n",
    "            for i in nums:\n",
    "                if nums.count(i) > 1:\n",
    "                    resList.append(i)\n",
    "        else:\n",
    "            for i in nums:\n",
    "                if i + k in nums:\n",
    "                    resList.append((i, i + k))\n",
    "                if i - k in nums:\n",
    "                    resList.append((i - k, i))\n",
    "        return len(set(resList))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        if k==0:\n",
    "            ret=0\n",
    "            for val in Counter(nums).values():\n",
    "                if val>1:\n",
    "                    ret+=1\n",
    "            return ret\n",
    "        myset=set(nums)\n",
    "        ret=set()\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]-k in myset:\n",
    "                ret.add((min(nums[i],nums[i]-k),max(nums[i],nums[i]-k)))\n",
    "            if nums[i]+k in myset:\n",
    "                ret.add((min(nums[i],nums[i]+k),max(nums[i],nums[i]+k)))\n",
    "        return len(ret)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    利用集合性质处理的解法\n",
    "    \"\"\"\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        set_nums = set(nums)\n",
    "        if k == 0:\n",
    "            return len(set([i for i in nums if nums.count(i) >= 2]))\n",
    "\n",
    "        nums_add_k = set([i + k for i in set_nums])\n",
    "        res = len(set_nums & nums_add_k)\n",
    "        return res\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     \"\"\"\n",
    "#     哈希表\n",
    "#     \"\"\"\n",
    "#     def findPairs(self, nums: List[int], k: int) -> int:\n",
    "#         dict_nums = defaultdict(int)\n",
    "#         for num in nums:\n",
    "#             dict_nums[num] += 1\n",
    "\n",
    "#         res = 0\n",
    "#         for item, value in dict_nums.items():\n",
    "#             if k == 0 and value >= 2:\n",
    "#                 res += 1\n",
    "#             elif k > 0 and (item + k) in dict_nums:\n",
    "#                 res += 1\n",
    "#         return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    利用集合性质处理的解法\n",
    "    \"\"\"\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        set_nums = set(nums)\n",
    "        if k == 0:\n",
    "            return len(set([i for i in nums if nums.count(i) >= 2]))\n",
    "\n",
    "        nums_add_k = set([i + k for i in set_nums])\n",
    "        res = len(set_nums & nums_add_k)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        visited, res = set(), set()\n",
    "        for num in nums:\n",
    "            if num + k in visited:\n",
    "                res.add((num+k, num))\n",
    "            if num - k in visited:\n",
    "                res.add((num, num-k))\n",
    "            visited.add(num)\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        vis=set()\n",
    "        res=set()\n",
    "        for c in nums:\n",
    "            if c+k in vis:\n",
    "                res.add((c,c+k))\n",
    "            if c-k in vis:\n",
    "                res.add((c-k,c))\n",
    "            vis.add(c)\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        s = set()\n",
    "        ans = set()\n",
    "        for num in nums:\n",
    "            if num - k in s:\n",
    "                ans.add((num-k, num)) # 因为没有顺序，可以不存元组，只保存较小的即可\n",
    "            if num + k in s: # 不能是elif， 因为这两个条件可能同时成立\n",
    "                ans.add((num, num+k))\n",
    "            s.add(num)\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        nums = sorted(nums)\n",
    "\n",
    "        check = collections.defaultdict(int)\n",
    "\n",
    "        memo = set()\n",
    "        ans = 0 \n",
    "        for x in nums:\n",
    "            if x-k in check and (x-k,x) not in memo:\n",
    "                ans += 1\n",
    "                memo.add((x-k,x))\n",
    "            check[x]+= 1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        vis=set()\n",
    "        res=set()\n",
    "        for c in nums:\n",
    "            if c+k in vis:\n",
    "                res.add((c,c+k))\n",
    "            if c-k in vis:\n",
    "                res.add((c-k,c))\n",
    "            vis.add(c)\n",
    "        return len(res)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPairs(self, nums: List[int], k: int) -> int:\n",
    "        num_set = set()\n",
    "        pair_set = set()\n",
    "        for num in nums:\n",
    "            if num - k in num_set:\n",
    "                pair_set.add((num-k, num))\n",
    "            if num + k in num_set:\n",
    "                pair_set.add((num, num+k))\n",
    "            num_set.add(num)\n",
    "        return len(pair_set)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
